class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();
        int sqr = sqrt(len);
        if(s.length() == 1) return false;
        if(check(s, 1)) return true;
        for(int i = 2; i <= sqr; i++)
        {
            if(len % i != 0) continue;
            int j = len / i;
            if(check(s, i) || check(s, j)) return true;
        }
        return false;
    }
    bool check(string s, int i) {
        for(int j = i; j < s.length(); j++)
        {
            int reminder = j % i;
            if(s[reminder] != s[j]) 
                return false;
        }
        return true;
    }
};

// a better solution
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s+s).find(s, 1) < s.length();
    }
};
